#include "definition.h"

class Solution {
 public:
  // 只能通过后序遍历
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && !right) return left;
    if (!left && right) return right;
    if (left && right) return root;
    return nullptr;  // if(!left&&!right)
  }
};

// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/c-jing-dian-di-gui-si-lu-fei-chang-hao-li-jie-shi-/

// 递归三部曲：
// 1. 确定递归函数功能，设计递归函数签名
// 2. 确定递归终止条件
// 3. 完成单层递归

// 重点：我们在调用递归函数的时候，把递归函数当做普通函数（黑箱）来调用
// ，即明白该函数的输入输出是什么，而不用管此函数内部在做什么。

// 本题函数有返回值，
// 是因为回溯的过程需要递归函数的返回值做判断，但本题我们依然要遍历树的所有节点。

// 因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。
// 与235题类似